package interview.eightqueens;

public class EightQueens {
	public void placeQuees(int n) {
		int[] queens = new int[n];
		if(place(0, n, queens)) {
			printBoard(n, queens);
		}
	}

	private void printBoard(int n, int[] queens) {
		for(int i = 0; i < n * n; i++) {
			System.out.print(queens[i / n] == i? "Q" : "*");
			System.out.print(" ");
			if(i % n == n - 1) {
				System.out.println();
			}
		}
	}

	private boolean place(int level, int n, int[] queens) {
		if (level >= n) {
			return true;
		}

		// iterate through all locations at row level
		for (int i = level * n; i < (level + 1) * n; i++) {
			if (canPlaceHere(i, queens, level, n)) {
				queens[level] = i;
				if (place(level + 1, n, queens)) {
					return true;
				}
			}
		}

		return false;
	}

	private boolean canPlaceHere(int position, int[] queens, int level, int n) {
		for(int i = 0; i < level; i++) {
			if(conflictWithQueue(position, queens[i], n)) {
				return false;
			}
		}
		return true;
	}

	private boolean conflictWithQueue(int position, int q, int n) {
		int row = q / n;
		int column = q % n;
		
		if(position / n == row) {
			return true;
		}
		
		if(position % n == column) {
			return true;
		}
		
		if(position / n - row == position % n - column) {
			return true;
		}
		
		if(row - position / n == position % n - column) {
			return true;
		}
		
		return false;
	}
}
